The increasing amount of data available in digital format requires developing appropriate data storage systems. In many cases, the amount of data to be stored exceeds the capacity of a single disk drive. Furthermore, the reliability of a single drive may not be sufficient for a particular application. This motivates the development of redundant disk arrays such as, for example, a Redundant Array of Independent Disks or RAID. The size of such arrays may vary from a few disks to a few thousand disks. A major challenge in their design is the development of efficient algorithms for calculating parity data, as well as for their recovery in case of disk failures. Such algorithms are based on encoding the data with some error/erasure correcting code (i.e., calculating parity data from the payload data), and storing different symbols of a codeword on different disks. That is, K disks are typically used to store the payload data, while N−K disks are used to store parity data, where N is the total number of disks in RAID group.
Numerous codes have been suggested for usage in storage applications, such as Reed-Solomon codes, Hamming codes, Remote Desktop Protocol, Even/Odd, Zigzag codes, etc. In general, the fraction (N−K)/N of parity disks needed to achieve given reliability decreases with the number of payload disks K. This motivates designing large disk arrays.
It is desirable to employ maximum distance separable (MDS) codes in the design of disk arrays. The crucial property of these codes is that they enable one to recover any combination of up to N−K erasures (disk failures). However, construction of MDS codes requires employing large alphabets. For example, Reed-Solomon codes and codes based on Cauchy matrices are defined over large finite fields GF(2m). The cost of the multiplication operation in such fields, which is needed for encoding and decoding of these codes, is much higher than that of the summation operation (exclusive-or, i.e., XOR). On the other hand, array codes are typically defined over the vector alphabet GF(2)m. Their encoding and decoding algorithms require exclusively XOR operation, but the size of one codeword (stripe size) is m times larger than that of codes over GF(2m). In a practical system, this results in more frequent partial stripe update operations, which considerably degrade RAID performance. As such, improved data encoding techniques are needed that utilize non-MDS codes.